package org.algorithm.Recursion;

import java.util.Arrays;

//插入排序
public class InsertionSortUseRecursion
{
    public void sort(int []array)
    {
        InsertionSort(array,1);
    }



    //low表示右侧未排序的下边界
    private void InsertionSort(int []array,int low)
    {
        if (low==array.length)
        {
            return;
        }

        int value = array[low];

        //
        int index = low-1;


        while (index>=0 && value<array[index])
        {
            array[index]=array[index+1];
            index--;
        }

        if (index+1!=low)
        {
            array[index+1]=value;
        }

        InsertionSort(array,low+1);
    }

    public static void main(String[] args) {
        int []array= {1,2,3,5,4,8,6,7};

        System.out.println(Arrays.toString(array));

        System.out.println("----------------");

        InsertionSortUseRecursion sortUseRecursion = new InsertionSortUseRecursion();

        sortUseRecursion.sort(array);
        System.out.println(Arrays.toString(array));

    }

}
